#!/usr/bin/env python
import re

class Matcher:
	def __init__(self):
		self.matches = {}
	def __call__(self,src,index = 0):
		for key in self.matches.keys():
			if key == (src,index):
				return self.matches[(src,index)]
		self.matches[(src,index)] = self.match(src,index)
		return self.matches[(src,index)]
	def __add__(self,other):
		if isinstance(other,str):
			other = Literal(other)
		elif isinstance(other,Structure):
			return other.__radd__(self)
		return Structure(self,other)
	def __radd__(self,other):
		if isinstance(other,str):
			other = Literal(other)
		return Structure(other,self)
	def __or__(self,other):
		if isinstance(other,str):
			other = Literal(other)
		elif isinstance(other,Union):
			return other.__ror__(self)
		return Union(self,other)
	def __ror__(self,other):
		if isinstance(other,str):
			other = Literal(other)
		return Union(other,self)

class Literal(Matcher):
	def __init__(self,string):
		self.matches = {}
		self.string = string
	def match(self,src,index):
		return [self.string] if src[index:].startswith(self.string) else None
	def __str__(self):
		return repr(self.string)
		
class Wildcard(Matcher):
	def __init__(self):
		self.matches = {}
	def match(self,src,index):
		return src[index] if index < len(src) else None
	def __str__(self):
		return '.'
			
class Range(Matcher):
	def __init__(self,low,high):
		self.matches = {}
		self.low = low
		self.high = high
	def match(self,src,index):
		return [src[index]] if self.low <= src[index] and src[index] <= self.high else None
	def __str__(self):
		return repr(self.low) + '-' + repr(self.high)

class Regexp(Matcher):
	def __init__(self,regexp):
		self.matches = {}
		self.matcher = re.compile(regexp)
	def match(self,src,index):
		match = self.matcher.match(src[index:])
		return [match.group()] if match != None else None
	# NOTE : This has a bug when matching regexps with forward slashes!
	def __str__(self):
		return '/' + self.matcher.pattern + '/'

# this class will combine ZeroOrOne, ZeroOrMore, and OneOrMore
class Repetition(Matcher):
	def __init__(self,matcher,lbound,ubound,separator):
		self.matcher = matcher
		self.lbound = lbound
		self.ubound = ubound
		self.separator = separator
	def match(self,src,index):	
		pass
			
class ZeroOrOne(Matcher):
	def __init__(self,matcher):
		self.matches = {}
		self.matcher = matcher
	def match(self,src,index):
		match = self.matcher(src[index])
		return match if match != None else []
	def __str__(self):
		return str(self.matcher) + '?'
	
class ZeroOrMore(Matcher):
	def __init__(self,matcher):
		self.matches = {}
		self.matcher = matcher
	def match(self,src,index):
		matches = []
		match = self.matcher(src,index)
		while match != None:
			matches += match
			index += sum(map(len,match))
			match = self.matcher(src,index)
		return matches
	def __str__(self):
		return str(self.matcher) + '*'
		
class OneOrMore(Matcher):
	def __init__(self,matcher):
		self.matches = {}
		self.matcher = matcher
	def match(self,src,index):
		matches = []
		match = self.matcher(src,index)
		if match == None:
			return None
		while match != None:
			matches += match
			index += sum(map(len,match))
			match = self.matcher(src,index)
		return matches
	def __str__(self):
		return str(self.matcher) + '+'
		
class Negation(Matcher):
	def __init__(self,matcher,unmatcher):
		self.matches = {}
		self.matcher = matcher
		self.unmatcher = unmatcher
	def match(self,src,index):
		match = self.matcher(src,index)
		if match != None:
			unmatch = self.unmatch(''.join(match),0)
			if unmatch != None:
				return match if ''.join(match) != ''.join(unmatch) else None
	def __str__(self):
		return matcher + '-' + unmatcher
		
class Structure(Matcher):
	def __init__(self,*matchers):
		self.matches = {}
		self.matchers = matchers
	def match(self,src,index):
		matches = []
		for matcher in self.matchers:
			match = matcher(src,index)
			if match == None:
				return None
			else:
				matches += match
				index += sum(map(len,match))
		return matches
	def __str__(self):
		return '(' + ', '.join(map(str,self.matchers)) + ')'
	def __add__(self,other):
		if isinstance(other,str):
			other = Literal(other)
		elif isinstance(other,Structure):
			value = Structure()
			value.matchers = self.matchers + other.matchers
			return value
		value = Structure()
		value.matchers = self.matchers + (other,)
		return value
	def __radd__(self,other):
		if isinstance(other,str):
			other = Literal(other)
		elif isinstance(other,Structure):
			value = Structure()
			value.matchers = other.matchers + self.matchers
			return value
		value = Structure()
		value.matchers = (other,) + self.matchers
		return value
		
class Union(Matcher):
	def __init__(self,*matchers):
		self.matches = {}
		self.matchers = matchers
	def match(self,src,index):
		for matcher in self.matchers:
			match = matcher(src,index)
			if match != None:
				return match
	def __str__(self):
		return '(' + ' | '.join(map(str,self.matchers)) + ')'
	def __or__(self,other):
		if isinstance(other,str):
			other = Literal(other)
		elif isinstance(other,Union):
			value = Union()
			value.matchers = self.matchers + other.matchers
			return value
		value = Union()
		value.matchers = self.matchers + (other,)
		return value
	def __ror__(self,other):
		if isinstance(other,str):
			other = Literal(other)
		elif isinstance(other,Union):
			value = Union()
			value.matchers = other.matchers + self.matchers
			return value
		value = Union()
		value.matchers = (other,) + self.matchers
		return value
				
class Node:
	def __init__(self,type,dictionary,string):
		self.type = type
		self.dictionary = dictionary
		self.string = string
	def __len__(self):
		return len(self.string)
	def __getitem__(self,key):
		if isinstance(key,str):
			return self.dictionary[key]
		elif isinstance(key,int):
			return self.string[key]
		raise ValueError()
	def keys(self):
		return self.dictionary.keys()
	def __str__(self):
		return self.string

class NodeMatcher(Matcher):
	# Pairs should be tuples of length 2 in form (name,matcher)
	# If there is no name, the name should be None
	def __init__(self,pairs):
		self.matches = {}
		self.pairs = pairs
	def match(self,src,index):
		dictionary = {}
		count = index
		for pair in self.pairs:
			match = pair[1](src,count)
			if match == None:
				return None
			elif isinstance(match,Node):
				count += len(str(match))
			else:
				count += len(''.join(map(str,match)))
			if pair[0] != None:
				self.dictionary[pair[0]] = match
		return dictionary,src[index:count]
	def __str__(self):
		def strPair(pair):
			if pair[0]:
				return pair[0] + ' = ' + str(pair[1])
			return str(pair[1])
		return ', '.join(map(strPair,self.pairs))
		
class Rule(Matcher):
	def __init__(self,type,matchers):
		self.type = type
		# all matchers should be NodeMatcher objects with same .type as self
		self.union = Union()
		self.union.matchers = matchers
	def match(self,src,index):
		dictionary,string = self.union.match(src,index)
		return Node(self.type,dictionary,string)

name = Regexp(r'[A-Za-z]+')
regex = Regexp(r'/([^/]|\\/)*/')
literal = Regexp(r"'([^']|\\.)*'")
classdefinition = name | regex | literal
number = Regexp(r'\d+')
quantifier = (Regexp(r'[?*+]') | '{' + number + ZeroOrOne(',' + number) + '}') + ZeroOrMore(classdefinition)
Class = classdefinition + ZeroOrOne(quantifier)
item = Class + ZeroOrOne(name)
structure = item + ZeroOrMore(',' + item)
expression = structure + ZeroOrMore('|' + structure)
statement = name + '=' + expression + ';'
root = OneOrMore(statement)
parse = lambda src : root(src,0)

if __name__ == '__main__':
	print(root)
